I'm being specific saying TSP-OP instead of TSP, because TSP could refer to a decision or search problem, for example "Is there a path shorter than x" (YES/NO), or "find a path shorter than x" (PATH). Both of these have results which are trivial to validate. The problem here, TSP-OP, is non-trivial to validate, as knowing if the found path is the shortest is as difficult as the original problem. For TSP, we can't guarantee global minima unless performing a costly a brute force search.
The ACO algorithm is an algorithm that finds near optimal solutions for the TSP-OP. Yet we can't guarantee the global minima. The input for the algorithm is a graph and the weights for each edges, which here will be the euclidian distance between the nodes in the plane. The output will be the path and it's distance. The steps toward the solution can also be seen as an output, as the "certainty" of the algorithm is represented by how quick it finds the solution as well as the presence of multiple paths being marked (the vizualisation of this process can be seen in the animation below)
All code below has been fully and solely created by me (Gabriel Nilsson)
# Run this cell to install networkx and plotly library
# Alternatively run "pip install networkx" in your cmd promt
import sys
!{sys.executable} -m pip install networkx
!{sys.executable} -m pip install plotly
# For Visualizations
from plotly.subplots import make_subplots
from IPython.display import clear_output
from matplotlib.pyplot import figure
import plotly.graph_objects as go
import matplotlib.pyplot as plt
import plotly.express as px
from ipywidgets import *
# Library for manipulating graphs
import networkx as nx
# Functional libraries
import random as rnd
import numpy as np
import math
import time
# Create Network
def CreateNetwork(amountNodes, createNew):
# Create graph, position nodes randomly
if createNew:
G = nx.complete_graph(amountNodes)
_pos = nx.random_layout(G)
else:
# Set graph and positions to global variables to copy last graph
# Used when doing multiple simulations on the same graph
G = network
_pos = pos
# Give each edge 2 attributes, weight and pheromone
for edge in G.edges():
startnode=edge[0]
endnode=edge[1]
if createNew:
# Set weight as euclidian distance according to pos
distances = round(math.sqrt(((_pos[endnode][1]-_pos[startnode][1])**2)+
((_pos[endnode][0]-_pos[startnode][0])**2)),2)
# Set pheromones to 1
G.add_edge(startnode, endnode, distance=distances, pheromone=1)
else:
# If not creating new, reset pheromones, distance will already be set
G.add_edge(startnode, endnode, pheromone=1)
# Return the network, and nodes positions
return G, _pos
def GetRandomPathRec(path):
# If path contains the whole network
# return
if len(path) == len(network.nodes):
return path
# Continue from last node
currentNode = path[-1]
# Available neighbors
possibleNext = []
# Neighbors individual probability weight for selection
probArr = []
# Append each available neighbor
for neighbor in list(network[currentNode]):
if neighbor not in path:
possibleNext.append(neighbor)
# Calculate individual prob using TraverseProb()
probArr.append(TraverseProb(currentNode, neighbor))
# Randomly select one neighbor
selection = rnd.random() * sum(probArr)
currI = -1
while selection > 0:
currI += 1
selection -= probArr[currI]
# Append selected neighbor
path.append(possibleNext[currI])
# Recursively return the rest of the path
return GetRandomPathRec(path)
def LengthOfPath(path):
# Calculate length of path
length = 0
# Increment with each distance of each edge
for i in range(len(path)):
length += network.edges[path[i], path[(i + 1) % len(path)]]['distance']
return length
def IncrementPheromones(path, value):
# Increment pheromone in each edge from path with value
for i in range(len(path)):
network.edges[path[i], path[(i + 1) % len(path)]]['pheromone'] += value
def TraverseProb(nodeA, nodeB):
# distance^-distBias * pheromone^pheroBias
# (-)distBias because more distance decrease probability
# We want bias toward closer nodes
return (pow(network.edges[nodeA, nodeB]['distance'], -distBias) *
pow(network.edges[nodeA, nodeB]['pheromone'], pheroBias))
# Draw the network
def DrawNetwork(pos, weights=[], text=""):
# Set size bounds for displaying network
figure(figsize=(10, 8), dpi=80)
# get the phermone of each edge
if weights == []:
# If weights not given, get weights of current network
weights = nx.get_edge_attributes(network, 'pheromone')
# Width of edge correspond to relative pheromone level
widths = np.array(list(weights.values()))
# Normalize widths
widths /= max(widths)
widths *= maxThickness
# Get nodes
nodelist = network.nodes()
# Draw nodes
nx.draw_networkx_nodes(network,pos,
nodelist=nodelist,
node_size=300,
node_color='red',
alpha=1)
# Draw Edges
nx.draw_networkx_edges(network,pos,
edgelist = weights.keys(),
width=widths,
edge_color='black',
alpha=1)
# Draw digits on nodes
nx.draw_networkx_labels(network, pos, font_size=10, font_color='white')
# Update title
if text:
plt.title(text)
plt.box(False)
plt.show()
def DisplayNetworkAnims(pos, index, snapshotInterval, doAnimation=True):
# Update function for interactive animation (graph).
# I put the Update function inside DisplayNetworkAnims() to get proper variable scope
# as this function should only be accesible in this function
def Update(step):
DrawNetwork(pos, pheroHistories[index][step],
f"Simulation {chr(index +65)}\nAnts simulated: {step * snapshotInterval}")
if doAnimation:
# Display animation
for i in range(len(pheroHistories[index])):
currentAnt = i * snapshotInterval # How many ants have been simulated at snapshot
clear_output(wait=True) # Clear output
DrawNetwork(pos, pheroHistories[index][i], f"Ants simulated: {currentAnt}") # Redraw new graph
time.sleep(.1) # Make it animate slowly
time.sleep(1)
clear_output(wait=True)
# interact() creates a interactive slider connected to the fuunction Update
print("You can click the slider and then use the left/right arrows to step through the process")
interact(Update, step=widgets.IntSlider(min=0, max=len(pheroHistories[index]) - 1, step=1, value=0))
# Draws a line graph describing the performance of the algorithm
def PerformanceGraph(antLen, average, bestLen):
# Create subplots depending on how many simulations have been performed (len(antLen) == amount of simulations)
# Have 2 graphs per row if simulations > 1
fig = make_subplots(rows=math.ceil(len(antLen) / 2), cols=1 if len(antLen) == 1 else 2)
avgFig = px.scatter()
# Boolean for displalying legend
displayLegend = True
for i in range(len(antLen)):
# Only display legend for first graph
if i == 1:
displayLegend = False
# Calculate current position among graphs
rowPos = (i // 2) + 1
colPos = i % 2 + 1
# Set titles for each graph
fig.update_yaxes(title_text="<b>Length of path</b><br>Unit is (100 km)s", row=rowPos, col=colPos)
fig.update_xaxes(title_text="<b>Ants simulated</b>", row=rowPos, col=colPos)
# Add trace for each line
# Each ants traversed distance
fig.add_trace(go.Scatter(y=antLen[i],
mode='lines',
name='Path length for each ant',
line_color='royalblue',
showlegend=displayLegend),
row = rowPos, col=colPos)
# Shortest path so far
fig.add_trace(go.Scatter(y=bestLen[i],
mode='lines',
name='Shortest path so far',
line_color='lightgreen',
showlegend=displayLegend),
row = rowPos, col=colPos)
# Critical termination line at 5% over the shortest path
fig.add_trace(go.Scatter(y=np.array(bestLen[i])*(1+terminationLine),
name='5% over shortest path',
line=dict(color='green', dash='dash'),
showlegend=displayLegend),
row = rowPos, col=colPos)
# Filled green area for shortest length
fig.add_trace(go.Scatter(
x=list(np.array(range(len(bestLen[i])))) +
list(np.array(range(len(bestLen[i]))))[::-1],
y=list(np.array(bestLen[i])*(1+terminationLine))+list(np.array(bestLen[i]))[::-1],
fill='toself',
fillcolor='rgba(107,231,103,0.3)',
line_color='rgba(255,255,255,0)',
showlegend=displayLegend,
name='5% region'),
row = rowPos, col=colPos)
# Running average of traversed distance
fig.add_trace(go.Scatter(x=np.array(range(len(antLen[i]))) + runningAvgOf//2,
y=average[i],
mode='lines',
name=f'Running average of path length (average of {runningAvgOf} ants)',
line_color='red',
showlegend=displayLegend),
row = rowPos,
col=colPos)
# Assign letter to each graph
fig.add_annotation(text=chr(i + 65),
xref="x domain", yref="y domain",
x=0.95, y=0.95, showarrow=False, row = rowPos, col=colPos, font_size=25)
# Only do running average graph if there are multiple simulations to compare
if len(average) > 1:
# avgFig is graph displaying each graphs running average
avgFig.add_trace(go.Scatter(x=np.array(range(len(antLen[i]))) + runningAvgOf//2,
y=average[i],
mode='lines+text',
name=f'Sim {chr(i + 65)} running average'))
# Layout settings for performance graphs
fig.update_layout(height=400*(math.ceil(len(antLen) / 2) + 1),
width=1000,
legend=dict(x=0, yanchor="bottom", y=-.15),
title_text='''<b>Linegraph showing performance of algorithm</b><br>
Distance of paths over amount of ants simulated''')
fig.show()
# Only do running average graph if there are multiple simulations to compare
if len(average) > 1:
# Set titles for running average graph
avgFig.update_yaxes(title_text="<b>Running average of paths</b><br>Unit is (100 km)s")
avgFig.update_xaxes(title_text="<b>Ants simulated</b>")
avgFig.update_layout(title_text='''<b>Linegraph showing running average of path length
over amount of ants simulated</b>''')
avgFig.show()
# Function for running ACO algorithm
def RunACO(nodesAmount,
distBias,
pheroBias,
evaporationRate,
pheromoneRate,
simulations = 1,
newNetwork=True):
# It is in general a bad practice to make variables global,
# as that might lead to unintended access/interactions with the variables,
# which can lead to logical errors which are difficult to find.
# I still choose to globalize these variables as to
# avoid being forced to tunnel them to the functions as parameters,
# this increases the readability of the code
global network
global pos
# These lists continuously store the relevant data for analysing the performance of the algorithm
# I globalize these variables for same reason as stated above.
global pheroHistories
global maxThickness
global antLenHistory
global bestLenHistory
global pheroHistory
global runningAvg
pheroHistories = []
globAntLenHistory = []
globBestLenHistory = []
globRunningAvgHistory = []
bestLengths = []
bestPaths = []
# Defining visual parameters
# All data later visualized are stored every 'snapshotInterval' ant
snapshotInterval=50
# Max thickness of the lines in the network
maxThickness = 8
# Set fontsize for network visualization
plt.rcParams.update({'font.size': 20})
# Globalized termination line for same reason as stated above
global terminationLine
# When the running average distance of the ants hit the line which is
# 'terminationLine' % above the shortest distance, it terminates. (bestL * (1+terminationLine))
terminationLine = .05
# Set minimum amount of ants to simulate, in the beginning of the simulation,
# the termination condition might be fulfilled, as the best path so far can be very high.
# Therefore we don't want to terminate if less than 'minimumAnts' have been smulated
minimumAnts = 100
# If the algorithm doesn't converge, we wish to terminate after 'maxAmountAnts' no matter what
maxAmountAnts = 10000
# A runningAvgOf 50 means that each value in the list runningAvg is the average of the 50 preceding values
global runningAvgOf
runningAvgOf=50
# For each simulation
for simiteration in range(simulations):
# The current 'runningAvgOf' values to average
# Works like a que, will be updated to always contain the most
# recent 'runningAvgOf' values from antLenHistory
currentFocus = []
# Storing pheromone values
pheroHistory = []
# Storing length of best path so far
bestLenHistory = []
# Storing length of each path created
antLenHistory = []
# Storing the running average of path lengths
runningAvg = []
# Store what the shortest path is
# Stores the order of the cities, listed by their index
bestPath = []
# Create network, only create new network first simulation
network, pos = CreateNetwork(nodesAmount, simiteration == 0)
# Set best length as large
bestL = 1000
for i in range(maxAmountAnts + 1):
# Evaporate pheromones each iteration
for edge in network.edges():
network.edges[edge]['pheromone'] *= (1 - evaporationRate)
# Put ant at random node
# Make ant go random path
path = GetRandomPathRec([rnd.randrange(nodesAmount)])
pathL = LengthOfPath(path)
# Fill up currentFocus until 'runningAvgOf' is reached
if i < runningAvgOf:
currentFocus.append(pathL)
else:
# After the first iterations
# Add the average to runningAvg
runningAvg.append(sum(currentFocus)/len(currentFocus))
# Add the new value to currentFocus
currentFocus.append(pathL)
# Remove the oldest value
currentFocus = currentFocus[1:]
# If the difference between the current runing average and the bestlength is
# within the termination percentage (5% in this case),
# and we've done at least 'minimumAnts' iterations,
# Terminate
if (runningAvg[-1] - bestL) / bestL < terminationLine and i > minimumAnts:
break
# If current path is shorter than shortest path
if pathL < bestL:
# Store new best path
bestL = pathL
bestPath = path
# Append current values to history lists
bestLenHistory.append(bestL)
antLenHistory.append(pathL)
# Store snapshot of pheromones at intervals
if i % snapshotInterval == 0:
pheroHistory.append(nx.get_edge_attributes(network, 'pheromone'))
# diff, how close to best seen solution
# Adding .001 to avoid division by zero
diff = pathL - bestL + .001
IncrementPheromones(path, pheromoneRate/diff)
# Store each history list in lists,
# So we can draw performance graphs on each simulation's history
globAntLenHistory.append(antLenHistory)
globBestLenHistory.append(bestLenHistory)
globRunningAvgHistory.append(runningAvg)
pheroHistories.append(pheroHistory)
bestLengths.append(round(bestL, 6))
bestPaths.append(bestPath)
# Only do the animation if we're doing a single simulation
if simulations == 1:
DisplayNetworkAnims(pos, 0, snapshotInterval, True)
# If simulating multiple times, draw each network, no animation
if simulations != 1:
for index in range(len(pheroHistories)):
DisplayNetworkAnims(pos, index, snapshotInterval, False)
# Draw the performance graph, for each simulation
PerformanceGraph(globAntLenHistory,
globRunningAvgHistory,
globBestLenHistory)
# Return the best paths and their lengths
return bestLengths, bestPaths
#Hyperparameters
nodesAmount=15
# Bias variables toward greedy and pheromone approach
distBias=2 # Increases bias toward choosing closer nodes
pheroBias=1 # Increase bias toward choosing pheromones, edges which have been traversed previously
# percentage of pheromones that evaporates each iteration
evaporationRate = .0001
# Coefficient for adding pheromones
pheromoneRate = .001
# Run this to see animation and one simulation
RunACO(nodesAmount,
distBias,
pheroBias,
evaporationRate,
pheromoneRate, 1)
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=38), Output()), _dom_classes=('widget-interac…
([2.89], [[3, 0, 5, 13, 6, 14, 11, 8, 2, 10, 7, 12, 1, 9, 4]])
# How many simulations to run on the same graph
simAmount = 6
# Run this to see multiple simulations
RunACO(nodesAmount,
distBias,
pheroBias,
evaporationRate,
pheromoneRate, simAmount)
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=14), Output()), _dom_classes=('widget-interac…
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=19), Output()), _dom_classes=('widget-interac…
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=9), Output()), _dom_classes=('widget-interact…
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=59), Output()), _dom_classes=('widget-interac…
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=16), Output()), _dom_classes=('widget-interac…
You can click the slider and then use the left/right arrows to step through the process
interactive(children=(IntSlider(value=0, description='step', max=15), Output()), _dom_classes=('widget-interac…
([3.47, 3.47, 3.47, 3.47, 3.47, 3.47], [[8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9], [3, 10, 0, 14, 7, 12, 4, 5, 11, 1, 13, 6, 2, 8, 9], [8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9], [8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9], [14, 0, 10, 3, 9, 8, 2, 6, 13, 1, 11, 5, 4, 12, 7], [8, 2, 6, 13, 1, 11, 5, 4, 12, 7, 14, 0, 10, 3, 9]])
Observe that we can see the length of the best path at the bottom of the output. When running multiple simulations we can see the stochastic component of this algorithm, as the final solution and the iterations required to get there varies for different smulatons on the same graph. We can see that the simulations that find a suboptimal solution also tend to be the ones that terminated early.
All line graphs above are interactive, you can select and deselect lines by clicking them in the legend. By clicking and dragging inside the graphs you can zoom in.
The algorithm simulates ants and how they in the real world find the best using pheromones. The concentration of pheromones is an emergent property of accumulated knowledge in the system. The core mechanic that makes this pathfinding work is that shorter paths will accumulate more pheromones as ants will walk there more frequently.
For each ant:
There are many ways one could design a termination condition. The goal of my termination condition is to correctly detect when the algorithm has "decided" upon a path, which I define as the probability of the algorithm "changing its mind" is decreasing and accellerating heavily. This event is very clear visibly in my animation, as the chosen paths edges become thicker, and all other edges practically disappear.
This is a good termination condition as running the simulation further would by definition not give a new solution, but only reinforce the one found. A negative is that we can't confirm that this will happen within a reasonable amount of time, for this reason I implemented a maximum amount of ants to simulate, as a secondary termination condition. This hyperparameter, much like the other hyperparameters, are dependent on the amount of nodes in the network, the computational time that is reasonable for the context, and the desired confidence.
When deciding on a termination condition I utilized the linegraph I produced which described the progress of the ants, this graph gave valuable insight on how to detect this event. First I considered only running for a predetermined amount of iterations only, which could be a sufficient condition depending on context, but clearly not effective as it sometimes would perform computation that has no effect on the result, and sometimes it would terminate before a path had been clearly desided upon. After examining the graph I noticed that the distribution of path-distances was "cut-off" approximately at the same time as when the desired effect could be visually seen in the animation. From this I added both the red and green line, the average distance of the paths and the shortet path found so far. With those additions it became apparent how the "deciding" event occured when a more significant portion of the ants took the best path found so far, which further reinforces it and further increases the amount of ants taking that path. When formulating the termination condition I considered:
Another termination condition that would be a more accurate representation of "one single path being chosen" is to see if the edges contained in the path are the only edges which are "activated", where not activated would be represented by edges having pheromone levels below some critical level. Where that critical level would be so low compared to the activated edges that they're effectively irrelevant. This would be a good termination condtion, but I judged it to be too costy to compute in each iteration, as I would have to check the levels of each edge every single iteration
The evaporation rate of the system is proportional to the current pheromone level, while the incrementation of pheromones is a constant value. This means that when the current pheromone levels are low, the impact of increasing pheromones will be relatively larger than the rate of evaporation. Vice versa is also true, if the pheromone levels are large the evaporation will be larger as well. Practically this means that an edge with less pheromones will, after being visited, get a more longer lasting impact than an edge that already has a lot of pheromones, there is a bias towards edges that are not visited that much, promoting any shorter paths found by random exploration. This effect is a balance against the effect that paths with more phermones will get visited a lot more. If the evaporation was not proportional, but had a constant value for decrementation, it would increase the probability that the algorithm would reinforce early solutions too heavily and settle on a local minima.
ACO is a stochastic optimization algorithm which, simular to simulated annealing, can find the global minima by allowing for random and temporary decrease in the objective function to fall into other basins that might lead to a better local minima, or perhaps even global minima (assuming we're looking to maximize). This is preferable over greedy and naive algorithms which have no process to avoid getting stuck in a local minima.
This stochastic property of course leaves the possibility for varying results on the same graph, therefore introducing the probability of suboptimal solutions. In ACO there are many small entities, ants, having a small impact on the system probabilities, pheromones. This in combination with the fact that better paths gets more pheromone than worse paths means that the only way for a suboptimal path to get chosen is for many random events "choosing" the less probable option. If path A is 1 units longer than the best path found so far, and path B is 2 units longer, then twice as many ants would have to randomly choose Path B than A for their pheromone levels to stay the same. Only if B is randomly selected more than twice as much in such succession so that its increased pheromone levels gives it twice the probability of being selected compared to A, only then could the pheromones take over to select a suboptimal path. This issue can be mitigated by decreasing the pheromones that ants spread, requiring mor e inprobable events in a row to hit this critical value. Relevant is also the evaporation rate, with a small evaporation rate, incorrectly enforced paths will stay for longer, increasing the chance of reinforcing the bad path. Following the logic above, we can control and decrease the probability of "accidentally" reinforcing a suboptimal solution by increasing the amount of ants, decreasing their individual pheromone spread, and increasing the fraction of pheromones that are evaporated.
ACO is clearly much more effective than both a greedy best first search (https://en.wikipedia.org/wiki/Best-first_search) and a brute force approach. The greedy best first would be very fast, especially if only run a single time, but has no process to avoid getting stuck in a local minima, which also means it often does not find the optimal solution, depending on the complexity of the problem. Brute force on the other hand will guaranteed find the best solution, although as it has a time complexity of O(n!), this algorithm becomes unfeasibly slow as n increases (n being the amount of nodes in the network). Greedy best first and brute force are on the two extremes on the balance between quality of result and time complexity. ACO has a much better balance, as it quickly eliminates large parts of the solution space while keeping a broad exploration.
Greedy best first search could also get stuck in local minima which are very bad solutions. If ACO gets stuck in local minima, it will with high probability be near optimal. Since the incrementing of the pheromones is proportional to the difference of the solutions and the best solution so far, it is much easier to get out of a local minima which is far away from best so far. Local minima that have a large difference of the objective function compared to the lowest point found so far become more volatile, or unstable. This stays true if the best solution found so far is close to the global minima, which is in general the case for ACO because of how it traverses the solution space. As covered in detail by (Gómez & Barán, n.d.), one of the reasons for ACOs success in TSP is its ability narrow down the soluton space. This can loosely be explained by the fact that near-optimal solutions for the TSP would share many edges, which is in ACOs favor as it's an edge selection based algorithm. Put in more concrete words, it's highly unprobable that there's a path which is significantly better than the best path found so far, which does not share any edges. Another way to phrase it is that the solution space has a convex structure at a larger scale.
Comparing a genetic algorithm (GA) and ACO is interesting as when you look at them conceptually, they in general build on similar principles when it comes to TSP (Gómez & Barán, n.d.). A similarity is that both algorithm can be seen as working with some kind of population, which has direct and combined impact on the further state. This is clear in GA, but also in ACO if you consider the edges as individual chromosomes, subject to high elitism. They performing crossover by increasing the probability that edges connected to a "high-pheromone" edge get searched, meaning that two "high-pheromone" edges can effectively merge, by increasing the amount of ants running over their nodes, and probabilisticly favoring the edges that connect these edges. Mutation, or exploration in the solution space, is performed by the random selections of each individual ant. These similarities are of course very conceptual, the largest practical difference are how this "crossover" and "mutation" is performed. The crossover in ACO is on a local scale, while GA does crossover between two whole paths. In ACO the crossover does not make large steps from the "parents" in the solution space, instead incremental steps which favor improving objective function, the negative of this is that it's not as exploratory as the GA crossover, which can mix entire paths in different ways. The mutation is also different, in ACO it has a very frequent but small effect, while in GA it's more rare but has more extreme effects (Depends on how it's perfromed, but a common approach, switching place of two cities, has a large impact on the objective function).
It has been shown that ACO outperforms GA in Path-finding problems which have similarity to TSP. In the test performed by (Sariff & Buniyamin, 2010), ACO was more than twice as fast in finding the optimized path.
There are multiple possible improvements for this algorithm. One is simply to run the algorithm multiple times with different hyperparameters, measuring the overall performance and finding the optimal hyperparameters for the specific use case. Another is simply performing the simulation in parallel, conecptually this could be like having multiple colonies of ants which are not affected by eachothers pheromones, this would decrease the probability of getting stuck in local minima (Manfrin et al., 2006). Another interesting example of an improvement is making the pheromone distribution rank-based, similar to rank-based selection in GAs, we would only allow the top $n$ ants spread pheromones, we could also make this pheromone spread proportional to the ants rank instead of its performance (Dorigo, 1999). More developed versions of ACO, and how they work, is covered by (Gómez & Barán, n.d.).
This algorithm relies on how the pheromone accumulation on the graph edges is an emergent property of learning between the ants. Every single ant walks pseudorandomly and sprouts pheromones in proportion to the reciprocal of distance traveled, no ant has any understanding of the overall path, they also don't learn anything as they don't adapt their behavior, they only follow the pheromones laid by other equally dumb ants. The incremental effect the pheromone has on the probabilites of following ants decisions lead to a positive feedback loop, reinforcing the edges which often take part in paths which end up short. No ant has any sense of the shortest path, but the pheromone concentration represents the collective learning of many ants and their decisions. This emergent property is exactly what we observe in the animation for the graph, where we can intuitively see how this collective learning adapts, changes it mind, has different certainty, and finally converges upon a reinforcing decision.
Binti Sariff, N., & Buniyamin, N. (2010). GENETIC ALGORITHM VERSUS ANT COLONY OPTIMIZATION ALGORITHM - Comparison of Performances in Robot Path Planning Application. Proceedings of the 7th International Conference on Informatics in Control, Automation and Robotics. https://doi.org/10.5220/0002892901250132
Dorigo, M. (1999, April). (PDF) ACO Algorithms for the Traveling Salesman Problem. ResearchGate. https://www.researchgate.net/publication/2771967_ACO_Algorithms_for_the_Traveling_Salesman_Problem
Gómez, O., & Barán, B. (n.d.). Relationship between Genetic Algorithms and Ant Colony Optimization Algorithms (p. Section 7.1). Retrieved March 7, 2022, from https://www.cnc.una.py/publicaciones/1_86.pdf
Manfrin, M., Birattari, M., Stützle, T., & Dorigo, M. (2006). Parallel Ant Colony Optimization for the Traveling Salesman Problem. Ant Colony Optimization and Swarm Intelligence, 224–234. https://doi.org/10.1007/11839088_20